package com.yangzhe.algorithm.c043;

// 超级回文数(java版)
// 如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
// 现在，给定两个正整数 L 和 R （以字符串形式表示），
// 返回包含在范围 [L, R] 中的超级回文数的数目。
// 1 <= len(L) <= 18
// 1 <= len(R) <= 18
// L 和 R 是表示 [1, 10^18) 范围的整数的字符串
//测试链接 : https://leetcode.cn/problems/super-palindromes/
public class Code02_SuperPalindromes {
    /**
     * 推测算法思路：超过 10 ^ 8肯定超时
     * 1. 全枚举  10^18 肯定超时，先开根号，枚举根号x是 10^9依然超时
     * 2. 枚举根号x前一半，然后组合成奇数和偶数根号x，例如 12，组合成1221和121两个根号x回文，然后分别平方，判断平方后的数x是不是回文，变成 枚举10^5，不会超时
     * <p>
     * 组合后 根号x 的范围是 根号left到根号right
     *
     * @param left
     * @param right
     * @return
     */
    public int superpalindromesInRange(String left, String right) {
        long l = Long.valueOf(left);
        long r = Long.valueOf(right);

        long limit = (long) Math.sqrt((double) r);
        long seed = 1;

        int result = 0;
        long enlargeNumber = 0;
        while (enlargeNumber <= limit) {

            // 偶数的回文
            enlargeNumber = evenEnlarge(seed);

            // 判断平方是否是回文
            if (check(enlargeNumber, l, r)) {
                result++;
            }
            // 奇数的回文
            enlargeNumber = oddEnlarge(seed);

            // 判断平方是否是回文
            if (check(enlargeNumber, l, r)) {
                result++;
            }
            seed++;
        }

        return result;
    }

    /**
     * 扩大成偶数回文
     *
     * @param seed
     * @return
     */
    public long evenEnlarge(long seed) {
        long result = seed;

        while (seed != 0) {
            result = result * 10 + seed % 10;
            seed = seed / 10;
        }

        return result;
    }

    /**
     * 扩大成奇数的回文
     *
     * @param seed
     * @return
     */
    public long oddEnlarge(long seed) {
        long result = seed;
        seed = seed / 10;

        while (seed != 0) {
            result = result * 10 + seed % 10;
            seed = seed / 10;
        }

        return result;
    }

    public boolean check(long num, long l, long r) {
        long x = num * num;
        return x >= l && x <= r && judgePalindrome(x);
    }

    /**
     * 判断数字是否是回文
     *
     * @param num 数字
     * @return 是否回文
     */
    public boolean judgePalindrome(long num) {
        // 整数中最大一位
        long offset = 1;
        while (num / offset >= 10) {
            offset = offset * 10;
        }

        while (num != 0) {
            // 最左和最右不相等不是回文
            if (num / offset != num % 10) {
                return false;
            }
            // 去掉最左
            num = num % offset;
            // 去掉最右
            num = num / 10;
            // 少了两个数量级
            offset = offset / 100;
        }

        return true;
    }


    public static void main(String[] args) {
        Code02_SuperPalindromes c = new Code02_SuperPalindromes();
        System.out.println(c.superpalindromesInRange("40000000000000000", "50000000000000000"));
    }

}
